class MedianFinder:
    def __init__(self):
        self.arr=[]
    def addNum(self, num):
        self.arr.append(num)
        self.arr.sort()
    def findMedian(self):
        length=len(self.arr)
        return self.arr[length//2] if length%2==1 else (self.arr[length//2]+self.arr[length//2-1])/2.0
# Your MedianFinder object will be instantiated and called as such:
# obj = MedianFinder()
# obj.addNum(-1)
# obj.addNum(-2)
# obj.addNum(-3)
# param_2 = obj.findMedian()
import heapq
class MedianFinder(object):

    def __init__(self):
        """
        initialize your data structure here.
        """
        self.left = []
        self.right = []
        self.median = None

    def addNum(self, num):
        """
        :type num: int
        :rtype: None
        """
        left, right = self.left, self.right
        if self.median is None:
            self.median = num
            return
        if num <= self.median:
            # 如果比中位数小，那么添在左边，且以其负数存储（这样在pop时可以取出最大值）
            heapq.heappush(left, -num)# heapq本质上是按照list来存储的
        else:
            heapq.heappush(right, num)

        if len(left) > len(right) + 1:
            top = -heapq.heappop(left)
            heapq.heappush(right, self.median)
            self.median = top
        if len(right) > len(left) + 1:
            top = heapq.heappop(right)
            heapq.heappush(left, -self.median)
            self.median = top

    def findMedian(self):
        """
        :rtype: float
        """
        left, right = self.left, self.right
        if len(left) == len(right):
            return self.median
        if len(left) > len(right):
            return (self.median - left[0]) / 2.0
        if len(right) > len(left):
            return (self.median + right[0]) / 2.0

# Your MedianFinder object will be instantiated and called as such:
# obj = MedianFinder()
# obj.addNum(num)
# param_2 = obj.findMedian()
from heapq import *


class MedianFinder:

    def __init__(self):
        """
        initialize your data structure here.
        """
        self.min_half = []
        self.max_half = []  # 可能会多一个数字

    def addNum(self, num):
        """
        :type num: int
        :rtype: void
        """
        num = float(num)
        if len(self.min_half) == len(self.max_half):
            heappush(self.max_half, -heappushpop(self.min_half, -num))# 右边多一个
        else:
            heappush(self.min_half, -heappushpop(self.max_half, num))# 两边相等

    def findMedian(self):
        """
        :rtype: float
        """
        if len(self.min_half) == len(self.max_half):
            return (-self.min_half[0] + self.max_half[0]) / 2
        else:
            return self.max_half[0]